- Title
- Hierarchical clustering using the arithmetic-harmonic cut: complexity and experiments
- Creator
- Rizzi, Romeo; Mahata, Pritha; Mathieson, Luke; Moscato, Pablo
- Relation
- Plos One Vol. 5, Issue 12
- Publisher Link
- http://dx.doi.org/10.1371/journal.pone.0014067
- Publisher
- Public Library of Science
- Resource Type
- journal article
- Date
- 2010
- Description
- Clustering, particularly hierarchical clustering, is an important method for understanding and analysing data across a wide variety of knowledge domains with notable utility in systems where the data can be classified in an evolutionary context. This paper introduces a new hierarchical clustering problem defined by a novel objective function we call the arithmeticharmonic cut. We show that the problem of finding such a cut is NP-hard and APX-hard but is fixed-parameter tractable, which indicates that although the problem is unlikely to have a polynomial time algorithm (even for approximation), exact parameterized and local search based techniques may produce workable algorithms. To this end, we implement a memetic algorithm for the problem and demonstrate the effectiveness of the arithmetic-harmonic cut on a number of datasets including a cancer type dataset and a corona virus dataset. We show favorable performance compared to currently used hierarchical clustering techniques such as k-MEANS, Graclus and NORMALIZED-CUT. The arithmetic-harmonic cut metric overcoming difficulties other hierarchal methods have in representing both intercluster differences and intracluster similarities.
- Subject
- clustering; hierarchical; arithmetic-harmonic; fixed-parameter
- Identifier
- uon:9497
- Identifier
- http://hdl.handle.net/1959.13/922157
- Identifier
- ISSN:1932-6203
- Full Text
- Reviewed
- Hits: 2567
- Visitors: 3358
- Downloads: 437
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT01 | Publisher version (open access) | 281 KB | Adobe Acrobat PDF | View Details Download |